﻿#include <iostream>
#include <vector>
#include <string>
using namespace std;

//int main() {
//    string str;
//    while (getline(cin, str))
//    {
//        vector<string> ret;
//        bool flag = false;//标记是否存在“”
//        string tmp;
//
//        for (auto ch : str)
//        {
//            if (ch == '"')
//                flag = !flag;
//            else if ((ch == ' ') && (!flag))
//                ret.push_back(tmp), tmp = "";
//            else
//                tmp += ch;
//        }
//        ret.push_back(tmp);
//        //输出打印
//        cout << ret.size() << endl;
//        for (auto _str : ret)
//            cout << _str << endl;
//    }
//}



//class Solution
//{
//	int tmp[50010];
//public:
//	int reversePairs(vector<int>& nums)
//	{
//		return mergeSort(nums, 0, nums.size() - 1);
//	}
//	int mergeSort(vector<int>& nums, int left, int right)
//	{
//		if (left >= right) return 0;
//		int ret = 0;
//		int mid = (left + right) >> 1;
//		// [left, mid] [mid + 1, right]
//		ret += mergeSort(nums, left, mid);
//		ret += mergeSort(nums, mid + 1, right);
//		//翻转对的数量
//		int cur1 = left, cur2 = mid + 1, i = left;
//		while (cur2 <= right) // 升序的情况
//		{
//			while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
//			if (cur1 > mid)
//				break;
//			ret += mid - cur1 + 1;
//			cur2++;
//		}
//		//有序数组
//		cur1 = left, cur2 = mid + 1;
//		while (cur1 <= mid && cur2 <= right)
//			tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//		while (cur1 <= mid) tmp[i++] = nums[cur1++];
//		while (cur2 <= right) tmp[i++] = nums[cur2++];
//		for (int j = left; j <= right; j++)
//			nums[j] = tmp[j];
//
//		return ret;
//	}
//};

class Solution
{
	vector<int> ret;
	vector<int> index; // 记录 nums 中当前元素的原始下标
	int tmpNums[500010];
	int tmpIndex[500010];
public:
	vector<int> countSmaller(vector<int>& nums)
	{
		int n = nums.size();
		ret.resize(n);
		index.resize(n);
		// 初始化index 数组
		for (int i = 0; i < n; i++)
			index[i] = i;
		mergeSort(nums, 0, n - 1);
		return ret;
	}

	void mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return;
		//划分区间
		int mid = (left + right) >> 1;
		// [left, mid] [mid + 1, right]
		// 处理左右两部分
		mergeSort(nums, left, mid);
		mergeSort(nums, mid + 1, right);
		//处理⼀左⼀右的情况
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right) // 降序
		{
			if (nums[cur1] <= nums[cur2])
			{
				tmpNums[i] = nums[cur2];
				tmpIndex[i++] = index[cur2++];
			}
			else
			{
				ret[index[cur1]] += right - cur2 + 1; 
				tmpNums[i] = nums[cur1];
				tmpIndex[i++] = index[cur1++];
			}
		}
		//剩下的排序过程
		while (cur1 <= mid)
		{
			tmpNums[i] = nums[cur1];
			tmpIndex[i++] = index[cur1++];
		}
		while (cur2 <= right)
		{
			tmpNums[i] = nums[cur2];
			tmpIndex[i++] = index[cur2++];
		}
		for (int j = left; j <= right; j++)
		{
			nums[j] = tmpNums[j - left];
			index[j] = tmpIndex[j - left];
		}
	}
};